// 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），
// 输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，
// 这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

const nextGreaterElements = function (nums: number[]): number[] {
    const stack: number[] = []; // 单调栈
    const res: number[] = new Array(nums.length).fill(-1); // 结果数组
    for (let i = 0; i < nums.length * 2; i++) {
        const currIndex = i % nums.length;
        while (stack.length > 0 && nums[currIndex] > nums[stack[stack.length - 1]]) {
            const stackPopIndex = stack.pop()!;
            res[stackPopIndex] = nums[currIndex];
        }
        stack.push(currIndex);
    }
    return res;
};


nextGreaterElements([1, 2, 1])


// 这道题目是一道非常好的考察单调栈使用的例题，代码书写难度不大
// 但难点在于需要找到正确的数据结构来解决此问题
// 首先考虑第一个问题，这道题目涉及到一个需要循环遍历数组的问题，怎么做？
// 题意要求是说数组的最后一个元素下一个元素是数组的第一个元素，形状类似于「环」。
// 一种比较巧妙地方式是给计数器声明乘2，然后使用取模运算可以把下标 i 映射到数组范围之内，这就解决了循环遍历的问题
// 然后针对这道题目的算法思路，很容易想到的是暴力破解方法，那是针对On2的复杂度而言，但并不能满足我们的需要
// 接下来应该注意到重要的部分应该是，如果数组的某一部分是单调不增的，那么会有很大的计算资源的浪费，
// 例如说[6,5,4,3,2,7],其中的6,5,4,3,2如果都需要往后遍历一遍才能找到7就非常的浪费
// 所以经过推论，可以先遍历循环数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），
// 我们就把这些元素保存，直到找到一个较大的元素；
// 然后把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」。
// 在实现上这里我们应该发觉可以使用单调栈来解决这道题目，单调栈具体存放的元素应该是数组下标
// 原因是有了数组下标就一定能知道原本的元素是什么，而下标还有额外定位数组元素位置的作用
// 在循环中做的事情也有了眉目：
// 建立「单调递减栈」，并对原数组遍历一次。
// 如果栈为空，则把当前元素放入栈内；
// 如果栈不为空，则需要判断当前元素和栈顶元素的大小：
// 如果当前元素比栈顶元素大：说明当前元素是前面一些元素的「下一个更大元素」，则逐个弹出栈顶元素，直到当前元素比栈顶元素小为止。
// 如果当前元素比栈顶元素小：说明当前元素的「下一个更大元素」与栈顶元素相同，则把当前元素入栈。
// 这里可以额外留意对于找不到「下一个更大元素」的元素处理，我们只需要把结果数组初始化为 -1 即可。
